package 剑指offer_leetcode;

/**
 * JZ35复杂链表的复制
 */
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class 剑指Offer35_复杂链表的复制 {
    public Node copyRandomList(Node head) {
        if(head==null)
            return null;
        Node cur = head;
        while(cur!=null){
            Node clon = new Node(cur.val);
            clon.next = cur.next;
            cur.next = clon;
            cur = clon.next;
        }
        Node res = head.next;
        Node clon = head.next;
        cur = head;
        while(cur!=null){
            if(cur.random==null)
                clon.random=null;
            else
                clon.random = cur.random.next;
            cur = cur.next.next;
            if(clon.next!=null)
                clon = clon.next.next;
        }
        cur = head;
        clon = head.next;
        while(cur!=null){
            cur.next = cur.next.next;
            cur = cur.next;
            if(clon.next!=null)
                clon.next = clon.next.next;
            clon = clon.next;
        }
        return res;
    }
}
